package com.fjl.stack.leetcode143;

import java.util.Stack;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/4/17 15:42
 */
/*
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */
public class Clazz {
    public void reorderList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (!stack.isEmpty()) {
            ListNode node = stack.pop();
            if (cur == node || cur.next == node) {
                // 这一步很关键，防止循环链表
                node.next = null;
                break;
            }
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
